Background: Saccharomyces cerevisiae is able to adapt to a wide range of external oxygen conditions. Previously, oxygen-dependent phenotypes have been studied individually at the transcriptional, metabolite, and flux level. However, the regulation of cell phenotype occurs across the different levels of cell function. Integrative analysis of data from multiple levels of cell function in the context of a network of several known biochemical interaction types could enable identification of active regulatory paths not limited to a single level of cell function. Results: The graph theoretical method called Enriched Molecular Path detection (EMPath) was extended to enable integrative utilization of transcription and flux data. The utility of the method was demonstrated by detecting paths associated with phenotype differences of S. cerevisiae under three different conditions of oxygen provision: 20.9%, 2.8% and 0.5%. The detection of molecular paths was performed in an integrated genome-scale metabolic and protein-protein interaction network. Conclusions: The molecular paths associated with the phenotype differences of S. cerevisiae under conditions of different oxygen provisions revealed paths of molecular interactions that could potentially mediate information transfer between processes that respond to the particular oxygen availabilities.